package mashibing.class14;

import java.util.PriorityQueue;

/**
 * 最少花费分割黄金（哈佛算法）
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-05-30
 */
public class Class14_2_LessMoneySplitGold {

    // 纯暴力！
    public static int lessMoney1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr, 0);
    }

    public static int process(int[] arr, int pre) {
        if (arr == null || arr.length <= 1) {
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int process = process(copyMergeArrays(arr, i, j), pre + arr[i] + arr[j]);
                ans = Math.min(ans, process);
            }
        }
        return ans;
    }

    public static int[] copyMergeArrays(int[] arr, int i, int j) {
        int[] copy = new int[arr.length - 1];
        int index = 0;
        for (int a = 0; a < arr.length; a++) {
            if (a != i && a != j) {
                copy[index++] = arr[a];
            }
        }
        copy[index] = arr[i] + arr[j];
        return copy;
    }

    // 贪心算法
    public static int lessMoney2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        int ans = 0;
        while (queue.size() > 1) {
            Integer poll1 = queue.poll();
            Integer poll2 = queue.poll();
            int money = poll1 + poll2;
            ans += money;
            queue.add(money);
        }
        return ans;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 6;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            if (lessMoney1(arr) != lessMoney2(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
